class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ret;
        int last[26]{0};    //记录每个字符的最后一次出现的下标

        for (int i = 0; i < s.size(); i++)
            last[s[i] - 'a'] = i;

        //使用双指针的思想
        //end为每一段的结束位置，start往后遍历，end不断更新
        //如果start碰到end，就说明[start, end]里面的字符不会再后面的地方出现
            //如果在后面又出现，那么end一定会在后面，不会被start追上
        int start = 0, end = 0;
        while (start < s.size())
        {
            end = last[s[start] - 'a'];
            int begin = start;
            while (begin != end)
            {
                begin++;
                end = max(end, last[s[begin] - 'a']);
            }

            ret.push_back(end - start + 1);
            start = end + 1;
        }

        return ret;
    }
};